package com.yulan.backTrack;


import java.util.ArrayList;
import java.util.List;

public class LeetCode_93 {
    public List<String> restoreIpAddresses(String s) {
        List<String> res = new ArrayList<>();
        StringBuilder cur = new StringBuilder();
        backtrack(s, 0, cur, 0, res);
        return res;
    }

    public void backtrack(String s,int index, StringBuilder cur, int depth, List<String> res){
        int len = cur.length();
        if(depth == 4){
            if(index == s.length()){
                cur.deleteCharAt(cur.length() - 1);
                res.add(cur.toString());
            }

            return;
        }
        for(int i = 1 ; i<=3 ;i++){
            if(index + i > s.length()) break;

            String str = s.substring(index,index+i);
            int num = Integer.parseInt(str);
            if(num > 255)
                break;

            if(String.valueOf(num).length()!=i)
                break;
            cur.append(str);

            cur.append(".");
            backtrack(s,index+i,cur,depth+1,res);
            cur.setLength(len);

        }
    }


}
